package 题目集.线段树or树状数组.线段树;

import java.io.*;
import java.util.Arrays;
import java.util.BitSet;

/**
 * https://www.luogu.com.cn/problem/P3740
 * 暴力思路：
 *      给每个海报加个id，贴一张海报时，相当于给区间l,r写入id。
 *      贴完后统计id的数量
 * 线段树：
 *      我们可以不要查询，认为只有区间写操作，最后遍历一次整棵树，求id得数量.
 *      这题的N范围很大，但操作的次数不多，可以把操作的次数看作值，对这些值离散化
 *      这题离散化也是个难点，因为是对区间离散化，所以需要给每个不连续的数中间加个值
 *      例如有3个区间，（3，12），（3，5），（10，12）.
 *      如果按传统离散化：会变为（1,4），(1,2)，（3，4）.会导致第一个区间（6，9）的部分消失
 *      给不连续的数加上一个值变为：(1，7)，（1,6）,(5,7)
 */
public class ch07_贴海报_区间离散化 {
    static Node[] tree;
    static int n, m, tn;
    static int size;
    static int[] sort;

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        m = sc.nextInt();
        sort = new int[m << 2]; //至多插入一倍，m的4倍

        int[][] ops = new int[m + 1][2];
        for (int i = 1; i <= m; i++) {
            ops[i][0] = sc.nextInt();
            ops[i][1] = sc.nextInt();
            sort[size++] = ops[i][0];
            sort[size++] = ops[i][1];
        }
        size = agge();

        tn = (int) Math.pow(2, 1 + Math.ceil(Math.log(size) / Math.log(2)));
        tree = new Node[tn];
        build(1, 1, size);

        for (int i = 1; i <= m; i++) {
            int l = rank(ops[i][0]);
            int r = rank(ops[i][1]);
            ops[i][0] = l;
            ops[i][1] = r;
            update(1, l, r, i);
        }

        int count = count();
        System.out.println(count);
    }

    public static int agge() {
        int size = 2 * m;
        Arrays.sort(sort, 0, size);
        //去重
        int cnt = 0;
        for (int i = 1; i < size; i++) {
            if (sort[i] != sort[cnt]) {
                sort[++cnt] = sort[i];
            }
        }
        size = cnt + 1;
        for (int i = 1; i < size; i++) {
            if (sort[i - 1] + 1 < sort[i]) {
                sort[++cnt] = sort[i - 1] + 1;  //在末尾补数
            }
        }
        size = cnt + 1;
        Arrays.sort(sort, 0, size);
        return size;
    }

    public static int rank(int v) {
        int l = 0, r = size - 1;
        while (l <= r) {
            int m = l + r >> 1;
            if (sort[m] < v) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return (l < size ? l : r) + 1;    //不越界返回l，l是刚好大于等于v
    }


    /**
     * 遍历整棵树，查看树上不同的编号数量
     * @return
     */
    public static int count() {
        int[] queue = new int[size + 2];
        BitSet count = new BitSet();
        int h = 0, t = 0;
        queue[t++] = 1;
        while (h != t) {
            int cur = queue[h];
            h = (h + 1) % queue.length;
            if (tree[cur].lazy) {
                count.set(tree[cur].id);
            } else {
                int l = cur << 1;
                int r = l | 1;
                if (l < tn && tree[l] != null) {
                    queue[t] = l;
                    t = (t + 1) % queue.length;
                }
                if (r < tn && tree[r] != null) {
                    queue[t] = r;
                    t = (t + 1) % queue.length;
                }
            }
        }
        return count.cardinality();
    }


    public static void build(int i, int l, int r) {
        tree[i] = new Node(l, r);
        if (l == r) return;
        int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
    }

    public static void update(int i, int l, int r, int v) {
        if (isLazy(i, l, r)) {
            updateLazy(i, v);
        } else {
            if (tree[i].lazy) {
                updateLazy(i << 1, tree[i].id);
                updateLazy(i << 1 | 1, tree[i].id);
                tree[i].lazy = false;
            }
            int m = tree[i].l + tree[i].r >> 1;
            if (l <= m) update(i << 1, l, r, v);
            if (m < r) update(i << 1 | 1, l, r, v);
            tree[i].id = 0; //表示下面不止一种节点，或者没有节点
        }
    }

    private static void updateLazy(int i, int id) {
        tree[i].id = id;
        tree[i].lazy = true;
    }

    public static boolean isLazy(int i, int l, int r) {
        return l <= tree[i].l && tree[i].r <= r;
    }

    static class Node {
        int l, r;
        int id;
        boolean lazy;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "l=" + l +
                    ", r=" + r +
                    ", id=" + id +
                    ", lazy=" + lazy +
                    '}';
        }
    }

    static class Reader {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }

        public long nextLong() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (long) in.nval;
        }
    }
}
